package Algorithm.sort;

import java.util.PriorityQueue;

/**
 * 215. 数组中的第K个最大元素 https://leetcode.cn/problems/kth-largest-element-in-an-array
 * 题目简述：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 */
public class FindKthLargest {

    /**
     * 思路一：堆排序。对数组进行扫描并使用一个最小堆保存当前最大的k个元素，堆顶最小即为当前第k大的元素，扫描完毕输出堆顶
     */
    public int findKthLargest(int[] nums, int k) {
        //创建容量为k的优先队列。然后开始扫描数组
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k);
        for (int num : nums) {
            //若队列当前元素数量小于k，则直接offer插入
            if (priorityQueue.size() < k)
                priorityQueue.offer(num);
            //否则与堆顶元素比较，若大于堆顶元素，则将堆顶元素移除再offer插入，维护TopK
            else if (num > priorityQueue.peek()){
                priorityQueue.poll();
                priorityQueue.offer(num);
            }
        }
        return priorityQueue.peek();//最后返回堆顶元素
    }

    /**
     * 思路二：快排中分区思想，分而治之。选择一个基准元素，将小于它的元素移动到左边，大于它的元素移动到右边，获得基准元素最终存放索引，
     *          若索引刚好等于n-k，则就是第k大的元素 直接输出
     *          若索引大于n-k，则在左半部分递归查找
     *          若索引小于n-k，则在右半部分递归查找
     */

}
